package ants;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import cell.Cell;

public class SimpleBFS {
  
  GameState gameState;
  
  
  public SimpleBFS(GameState gsIn) {
    gameState = gsIn;
  }
  
  
  public Cell simpleSearch(int maxDepth, Cell m, CellProperty targetType) {
   // Logger.log("beginning search from " + m.row + " " + m.col);
    List<Cell> frontier = new ArrayList<Cell>( );
    frontier.add(m);
    Set<Cell> seen = new HashSet<Cell>( );
    Map<Cell, Cell> predecessors = new HashMap<Cell, Cell>( );
    Map<Cell, Integer> pathLengths = new HashMap<Cell, Integer>( );
    pathLengths.put(m, 0);
    
    return simpleSearchRecursive(frontier,
                                 targetType, seen, maxDepth,
                                 new HOF.Function_1<Cell, Boolean>( ) {
                                   public Boolean apply(Cell m) {
                                     return (gameState.isWater(m) || gameState.isMyAnt(m));
                                   }
                                   
                                 }, predecessors, pathLengths);
    
    
  }
  
  
  public Cell simpleSearchRecursive(
                                    List<Cell> frontier, // sometimes called
                                                         // "open"
                                    CellProperty targetType,
                                    Set<Cell> seen, // sometimes called "closed"
                                    int maxDepth,
                                    HOF.Function_1<Cell, Boolean> isBlocked,
                                    Map<Cell, Cell> predecessors,
                                    Map<Cell, Integer> pathLengths) {
    
       
    if (frontier.isEmpty( )) {
     // Logger.log("BFS terminated with no goal found ");
      return null;
    }
    
    Cell currNode = frontier.remove(0);
    if (pathLengths.get(currNode) > maxDepth) return null;

//    Logger.log("removed " + currNode.row + " " + currNode.col + " from frontier");
    List<Cell> newFrontier = new ArrayList<Cell>( );
    newFrontier.addAll(frontier);
    for (Cell m: gameState.getLandNeighbors(currNode))
      if (!(seen.contains(m))) {
        seen.add(m);
        predecessors.put(m, currNode);
        if (gameState.hasProperty(targetType, m)) {
  //        Logger.log("found " + targetType.toString( ) + " at " + m.row + " " + m.col);
          return m;
          
        } else if (!(isBlocked.apply(m))) {
          newFrontier.add(m);
       //   Logger.log("adding " + m.row + " " + m.col + " to frontier");
          
          pathLengths.put(m, pathLengths.get(currNode) + 1);
         // Logger.log("adding succ: " + m.row + " " + m.col + " pred: " + currNode.row + " "
           //          + currNode.col + " to predecessors");
        }
      }
      else if(pathLengths.containsKey(m)){
        int length = pathLengths.get(m);
        int newLength = pathLengths.get(currNode) + 1;
        if (length > newLength) {
          pathLengths.remove(m);
          pathLengths.put(m, newLength);
        }
      }

    
    Set<Cell> newSeen = new HashSet<Cell>( );
    newSeen.addAll(seen);
    newSeen.add(currNode);
    
    return simpleSearchRecursive(newFrontier,
                                 targetType, newSeen, maxDepth,
                                 new HOF.Function_1<Cell, Boolean>( ) {
                                   public Boolean apply(Cell m) {
                                     return (gameState.isWater(m) || gameState.isMyAnt(m));
                                   }
                                   
                                 }, predecessors, pathLengths);
    
  }
  
  
  public int countTargets(int maxDepth, Cell m, final CellProperty targetType) {
    //Logger.log("beginning count targets search from " + m.row + " " + m.col);
    int count = 0;
    List<Cell> frontier = new ArrayList<Cell>( );
    frontier.add(m);
    Set<Cell> seen = new HashSet<Cell>( );
    Map<Cell, Cell> predecessors = new HashMap<Cell, Cell>( );
    Map<Cell, Integer> pathLengths = new HashMap<Cell, Integer>( );
    pathLengths.put(m, 0);
    return countTargetsRecursive(frontier,
                                 targetType, seen, maxDepth,
                                 new HOF.Function_1<Cell, Boolean>( ) {
                                   public Boolean apply(Cell m) {
                                     return (gameState.isWater(m) || gameState.hasProperty(targetType, m));
                                   }
                                   
                                 }, predecessors, pathLengths, count);
    
    
  }
  
  
  public int countTargetsRecursive(
                                   List<Cell> frontier, // sometimes called
                                                        // "open"
                                   CellProperty targetType,
                                   Set<Cell> seen, // sometimes called "closed"
                                   int maxDepth,
                                   HOF.Function_1<Cell, Boolean> isBlocked,
                                   Map<Cell, Cell> predecessors,
                                   Map<Cell, Integer> pathLengths, int count) {
    //Logger.log("looking for targets of type " + targetType.toString( ) + " max depth: " + maxDepth);
    
    
    if (frontier.isEmpty( )) {
      //Logger.log("empty frontier");
      return count;
    }
        
    Cell currNode = frontier.remove(0);
    if (pathLengths.get(currNode) > maxDepth) return count;
    //Logger.log("removed " + currNode.row + " " + currNode.col + " from frontier");
    List<Cell> newFrontier = new ArrayList<Cell>( );
    newFrontier.addAll(frontier);
    for (Cell m: gameState.getLandNeighbors(currNode)) {
      
      if (!(seen.contains(m))) {
        seen.add(m);
        predecessors.put(m, currNode);
        
      //  Logger.log(m.row + " " + m.col + ": " + targetType.toString( ) + "? " + gameState.hasProperty(targetType, m));
        
        if (gameState.hasProperty(targetType, m)) {
          //Logger.log("found " + targetType.toString( ) + " at " + m.row + " " + m.col);
          count += 1;
          
        } else if (!(isBlocked.apply(m))) {
          newFrontier.add(m);
        //  Logger.log("adding " + m.row + " " + m.col + " to frontier");
          
          pathLengths.put(m, pathLengths.get(currNode) + 1);
          //Logger.log("adding succ: " + m.row + " " + m.col + " pred: " + currNode.row + " "
            //         + currNode.col + " to predecessors");
        }
      }
      else if(pathLengths.containsKey(m)){
        int length = pathLengths.get(m);
        int newLength = pathLengths.get(currNode) + 1;
        if (length > newLength) {
          pathLengths.remove(m);
          pathLengths.put(m, newLength);
        }
      }
//      Logger.log(m.row + " " + m.col + " depth: " + pathLengths.get(m));
      
    }
    
    Set<Cell> newSeen = new HashSet<Cell>( );
    newSeen.addAll(seen);
    newSeen.add(currNode);
    
    return countTargetsRecursive(newFrontier,
                                 targetType, newSeen, maxDepth,
                                 new HOF.Function_1<Cell, Boolean>( ) {
                                   public Boolean apply(Cell m) {
                                     return (gameState.isWater(m) || gameState.isMyAnt(m));
                                   }
                                   
                                 }, predecessors, pathLengths, count);
    
  }
  
  
  
}
